﻿#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution
{
public:
    // 553. 最优除法
    string optimalDivision(vector<int>& nums)
    {
        int n = nums.size();
        string ret;
        if (n == 1)
        {
            ret += to_string(nums[0]);
        }
        else if (n == 2)
        {
            ret += to_string(nums[0]) + "/" + to_string(nums[1]);
        }
        else
        {
            ret += to_string(nums[0]) + "/(" + to_string(nums[1]);
            for (int i = 2; i < n; ++i)
                ret += "/" + to_string(nums[i]);
            ret += ")";
        }
        return ret;
    }

    // 45. 跳跃游戏 II
    /*int jump(vector<int>& nums)
    {
        int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
        while (left <= right)
        {
            if (maxPos >= n - 1)
                return ret;
            for (int i = left; i <= right; ++i)
                maxPos = max(maxPos, nums[i] + i);
            left = right + 1;
            right = maxPos;
            ret++;
        }
        return 0;
    }*/

    int jump(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n, 0x3f3f3f3f);

        dp[0] = 0;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (j + nums[j] >= i)
                    dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        return dp[n - 1];
    }
};

int main()
{
    /*vector<int> v{ 1000,100,10,2 };
    cout << Solution().optimalDivision(v) << endl;*/

    vector<int> v{ 2,3,1,1,4 };
    cout << Solution().jump(v) << endl;

    return 0;
}